The present invention relates to a Montgomery transform device, an arithmetic device, an IC card, an encryption device, a decryption device and a program which are small-sized and capable of being incorporated in an IC card (smart card).
A public key encryption system is one of the most important techniques among encryption techniques. An encryption system, for example, Rivest-Shamir-Adleman (RSA) encryption, a digital signature algorithm (DSA) signature and the like have been widely used. In recent years, a public key encryption system has become able to execute the RSA signature on the IC card; then, the application field of security has spread. However, a usual IC card has a CPU with a low performance, so that a single CPU requires too much time for performing signature processing. Therefore, an IC card for encryption additively has an arithmetic device referred to as an encryption accelerator or a coprocessor so as to reduce the time necessary for the signature processing.
A leading public key encryption system is composed of arithmetic calculation on a finite field. An arithmetic object is, for example, a multi-precision integer of 1,024 bits, etc. Here, many arithmetic techniques to make the encryption accelerator miniaturize and accelerate have been developed. An especially important arithmetic technique is a system using the Chinese remainder theorem (CRT) and Montgomery reduction. CRT and Montgomery reduction are described in detail by, for example, A. J. Menezes, P. C. van Oorshot, and S. A. Vanstone, “Handbook of applied cryptography”, CRC Press, section 14, etc., (1997).
CRT can execute calculation on a subfield and reduce calculation time by supposing that factorization for a modulus has been already known. In the case of the RSA encryption, since it is assumed that a modulus n can be factorized into two prime numbers p and q, so that a calculation result of mod n (=mod pq) can be calculated on the basis of calculation results of mod p and mod q. In this case, since a whole of intermediate calculation can be done by an extent of almost a half number of digits, a calculation amount is reduced.
Montgomery reduction can calculate a remainder necessary for calculation on the finite filed only by multiplication without division. Generally, division is less advantageous than multiplication in points of a circuit size and an arithmetic speed. Montgomery reduction does not use the division, thereby, advantageous in miniaturization and speeding up. An algorithm in the division calculates a partial quotient when obtaining a remainder. If calculation efficiency for the partial quotient is tried to be enhanced, an error is generated and trial and error such as a re-addition and a re-subtraction are required. This is the reason why the division is disadvantageous.
Both CRT and Montgomery reduction are techniques useful for increasing efficiency and separated with each other, so that it is possible for both CRT and Montgomery reduction can be combined together.
FIG. 1 is a schematic diagram showing a logical configuration to calculate a power remainder by using CRT and Montgomery reduction. The calculation for the power remainder is defined as a content to execute an input m to the d-th power under a modulus pq. In an arithmetic device, mod(remainder calculation) arithmetic units 1 and 2 calculate remainders mp (=m mod p) and mq (=m mod q) for an input m of 2n-bit and a power exponent d and obtain remainders mp and mq of n-bit, respectively.
Next, for Montgomery transform units 3 and 4 perform the Montgomery transform of the remainders mp and mq, preparatory for using Montgomery arithmetic and obtain transform results mp′ (=m×Rp mod p) and mq′(=m×Rq mod q), respectively.
At this time, the Rp and the Rq are constants calculated in advance. The constant Rp is the power of 2 larger than the prime number p and a value to make a bit shift instead of the division during Montgomery reduction. In similarity, the constant Rq is the power of 2 larger than the prime number q.
Next, Montgomery power units 5 and 6 calculate power remainders using Montgomery reduction to the transform results mp′ and mq′, respectively, and obtain power remainders sp′ (=mp′^dp×Rq mod p) and Sq′ (=mq′^dq×Rq mod q), respectively. However, dp=d mod(p−1) and dq=d mod(q−1). The power exponents dp and dq are assumed that they are calculated in advance. A symbol ^ indicates the power.
Since the power remainders sp′ and Sq′ are values on the Montgomery space, they should be returned to values on the finite field. Consequently, Montgomery inverse transform units 7 and 8 perform the Montgomery inverse transform to the power remainders sp′ and Sq′ and obtain power remainders sp (=s mod p) and sq (=s mod q) on the finite field, respectively.
After this, a CRT arithmetic unit 9 solves simultaneous equations of the sp (=s mod p) and the sq (=s mod q) of n-bit on the basis of CRT and obtains s=s mod pq as a solve s of 2n-bit. This solve s has become a power remainder s=md mod pq of a final result.
Power remainder calculation has just completed as mentioned above. In practice, the prime numbers p and q are set to around 512 bits and the input m is set to around 1,024 bits to assure security.
However, such an arithmetic device described above requires remainder calculation (mod arithmetic) for reducing the number of bits in an input stage so as to combine CRT and Montgomery arithmetic.
The reason of the necessity of the remainder calculation is considered that the Montgomery transform units 3 and 4 accept the inputs mp and mq of n-bit but do not accept the input m of 2n-bit. However, the remainder calculation requires the division to obtain a remainder. As stated above, the division is disadvantageous in the points of the circuit size and the arithmetic speed.